package org.example;

import java.util.Stack;

public class Test4 {
    //leetcode 844 比较含退格的字符串 https://leetcode.cn/problems/backspace-string-compare/

    /**
     * 方法一：使用栈来解决
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();
        backspace(stack1,s);
        backspace(stack2,t);
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.pop() != stack2.pop()) return false;
        }
        if (!stack1.isEmpty() || !stack2.isEmpty()) return false;
        return true;
    }

    public void backspace(Stack<Character> stack,String s) {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#') {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            }else {
                stack.add(c);
            }
        }
    }

    /**
     * 方法二：通过StringBuilder来记录退格之后的字符串
     * @param s
     * @param t
     * @return
     */
    public boolean backspaceCompare2(String s, String t) {
        return backspace(s).equals(backspace(t));
    }

    public String backspace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#') {
                if (sb.length() != 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
